package com.berchen.offer;

/**
 * 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
 * 如果o2 是o1的子树中的节点 那么o1 o2的最近父节点就是o1
 * <p>
 * 数据范围：1 \le n \le 10001≤n≤1000，树上每个节点的val满足 0<val \le 1000<val≤100
 * 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 * <p>
 * 注：本题保证二叉树中每个节点的val值均不相同。
 */
public class Test14 {
    /**
     * 其实就是找 节点是否包含两节点 如果是 那么该节点就是最近的
     *
     * @param root
     * @param o1
     * @param o2
     * @return
     */
    public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
        // write code here

        return diGUI(root, o1, o2).val;

    }

    /**
     * 如果o2 是o1的子树中的节点 那么o1 o2的最近父节点就是o1
     * 根 左 右 遍历的顺序
     * @param node
     * @param o1
     * @param o2
     * @return
     */
    TreeNode diGUI(TreeNode node, int o1, int o2) {

        // 如果root为空，或者root为o1、o2中的一个，则它们的最近公共祖先就为root
        if (node == null || node.val == o1 || node.val == o2) {
            return node;
        }

        TreeNode left = diGUI(node.left, o1, o2);
        TreeNode right = diGUI(node.right, o1, o2);
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else {
            return node;
        }

    }
}
